import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.regex.Matcher;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution56 {

    public static void main(String args[]) {
        Solution56 s = new Solution56();
    }

    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> ret = new ArrayList<>();
        if (intervals.size() == 0) {
            return ret;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start == o2.start) {
                    return o1.end - o2.end;
                }
                return o1.start - o2.start;
            }
        });

        int s = intervals.get(0).start;
        int e = intervals.get(0).end;

        for (int i = 1; i < intervals.size(); i++) {
            Interval it = intervals.get(i);
            if (e >= it.start) {
                e = Math.max(it.end, e);
                continue;
            } else {
                ret.add(new Interval(s, e));
                s = it.start;
                e = it.end;
            }
        }

        ret.add(new Interval(s, e));
        return ret;
    }

}














